gamesandsimulationsfandomcom-20200213-history
Splines
Introduction Generally speaking, a spline is a polynomial curve. In the context of computer graphics, this is attractive in several ways; first, points on the spline, tangents, normals and binormals can be evaluated easily and efficiently, using only arithmetic operations. Second, it is usually possible to solve for a specific polynomial that fits some set of sample data, boundary conditions, and/or various other constraints -- which makes it fairly straightforward to derive specific splines for specific tasks, and helps explain the sheer number of different spline types. Third, splines easily generalize to higher dimensions, as spline surfaces and, more generally, spline lattices. Finally, low-degree splines behave very predictably, making them a useful tool in modelling and animation. Endpoint and tangent conditions There are two complementary ways of looking at how splines "work"; one leads to cubic Hermite splines, another leads to Bezier splines. We start with the first one. A spline of degree N is a vector-valued polynomial of the same degree. This can be written as P(t) = c_0 + c_1 t + c_2 t^2 + ... + c_N t^N , where the coefficients c_i are vectors, and the scalar t is usually assumed to run from 0 to 1 . There are N+1 coefficients; in order to determine them uniquely, we need N+1 independent constraints. Since two constraints are generally known a priori (the endpoints P(0) and P(1) are prescribed), this leaves N-1 constraints required in order to define a spline of degree N . More specifically, to obtain a quadratic spline, we need one extra condition, to obtain a cubic spline we need two, and so forth. One natural set of constraints is to prescribe the tangents at both endpoints, which is useful if we want to piece together segments of splines; the lowest degree spline that can satisfy these conditions in general is 4 - 1 = 3 . The resulting spline is the cubic Hermite spline, and the coefficients can be determined as follows. First, let H(t) = At^3+Bt^2+Ct+D , where A, B, C and D are the coefficients to be solved for. Differentiating to obtain the tangent at t , we get H'(t) = \frac{dH}{dt} = 3At^2+2Bt+C . Let four points P_1, P_2, P_3 and P_4 be given, with P_1 and P_4 being the endpoints of the spline, and the tangents given as P_2-P_1 and P_4-P_3 respectively. Then the conditions can be expressed as and solving this gives Further control over the shape of the curve can be obtained by scaling H'(0) and H'(1) by some factor. Picking a common factor for both leads to the so-called cardinal splines, which are Hermite splines with a tension factor c. The tangency conditions then become H'(0) = (1-c)(P_2-P_1) and H'(1) = (1-c)(P_4-P_3) . Letting c=\frac{1}{2} gives Catmull-Rom splines. Letting c=0 gives regular Hermite splines. Letting c=1 gives lines. Letting c=-2 results in the cubic Bezier splines, as we'll see shortly. Polynomial bases Taking from the previous section the idea of prescribing tangent conditions, we can arrive at a generalization (or rather, arrive at the possibility of a generalization) as follows. Recall the definition of H(t) -- this was H(t) = At^3 + Bt^2 + Ct + D . Plugging in the values for A, B, C and D gives H(t) = (P_1+P_2-P_3-P_4)t^3 + (-P_1-2P_2+P_3+2P_4)t^2 + (P_2-P_1)t + P_1 . We can regroup the terms by P_i , which gives H(t) = (t^3-t^2-t+1) P_1 + (t^3-2t^2+t) P_2 + (-t^3+t^2) P_3 + (-t^3+2t^2) P_4. This suggests that H(t) can be viewed as the sum of four polynomials, each of them weighed by a control point. Examining the polynomial corresponding to P_1 , we see that it is equal to one at t=0 , and equal to zero at t=1 . Similarly, the polynomial corresponding to P_4 starts at 0 , and goes to 1 . That is, P_1 is fully contributing to the sum at t=0 , and not contributing at all at t=1 -- and vice versa for P_4 . This certainly makes sense, since the curve has to pass through both points, and the remaining two polynomials are zero at the endpoints. Further, it is useful to consider the sum of the four polynomials without the weights P_1, P_2, P_3 and P_4 applied; if they add up to one, then we can say that H(t) is a weighted average of its' control points for every t . Straightforward algebra proves this to be the case, which suggests a generalization that would work with arbitrary degree splines. All that is required, for a particular spline degree n , is a family of n+1 polynomials that adds up to 1 on the interval 0,1 , and contains one polynomials that goes from 0 to 1 , and another polynomial that goes in the opposite direction. One such family is the Bernstein polynomials. These are defined as B_{k,n}(t) = {n\choose k} t^k (1-t)^{n-k} , where {n\choose k} is the binomial coefficient and 0^0 is taken to be 1 . The definition satisfies the requirements given in the previous paragraph, and weighing n control points by the Bernstein polynomials of degree n results in the generalization that was being sought. The resulting curve, given as \sum_{i=0}^n P_{i+1} B_{i,n} is known as the Bezier curve with n control points. For n=3 , this reduces to the cardinal spline with c=-2 , which is easily verified by expanding the sum.